import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2022-10-04
 * Time: 18:02
 */
public class Queue_Stack {
    //用双队列实现 一个 后入先出 得栈

    public Queue<Integer> qu1 ;
    public Queue<Integer> qu2 ;

    public Queue_Stack(){
        //队列是一个接口 在实例化队列时，必须实例化LinkedList对象 -- 因为LinkedList 实现了Queue 接口
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }

    // 压栈
    public void push(int x) {
        // 两个队列 谁空先放谁
        if(!qu1.isEmpty()){
            qu1.offer(x);
        } else if (!qu2.isEmpty()) {
            qu2.offer(x);
        }else {
            // 均为空 默认放qu1
            qu1.offer(x);
        }
    }

    //出栈
    public int pop() {

        if(!qu1.isEmpty()) {
            //将当前size-1个元素从队列中弹出
            int size = qu1.size();
            for (int i = 0; i < size-1; i++) {
                //将qu1 每一个弹出得 存放在 qu2
                qu2.offer(qu1.poll());
            }
            // 最后一个元素即为当前 后入先出栈得弹出元素
            return qu1.poll();
        }else if(!qu2.isEmpty()) {
            int size = qu2.size();
            for (int i = 0; i < size-1; i++) {
                qu1.offer(qu2.poll());
            }
            return qu2.poll();
        }else {
            return -1;
        }
    }

    public int top() {
        if(!qu1.isEmpty()) {
            //将 当前 size个元素全部弹出
            int size = qu1.size();
            int ret = -1; // 记录每次弹出得结果
            for (int i = 0; i < size; i++) {
                ret = qu1.poll();
                // 放到另一个队列中
                qu2.offer(ret);
            }
            // 最后一个元素即为当前 后入先出栈得弹出元素
            return ret;
        }else if(!qu2.isEmpty()) {
            int ret = -1;
            int size = qu2.size();
            for (int i = 0; i < size; i++) {
                ret = qu2.poll();
                qu1.offer(ret);
            }
            return ret;
        }else {
            return -1;
        }
    }

    // 空栈
    public boolean empty() {
        return qu2.isEmpty() && qu1.isEmpty();
    }

}
